Harmony search

In computer science and operations research, harmony search (HS) is a phenomenon-mimicking algorithm (also known as metaheuristic algorithm, soft computing algorithm or evolutionary algorithm) inspired by the improvisation process of musicians. In the HS algorithm, each musician (= decision variable) plays (= generates) a note (= a value) for finding a best harmony (= global optimum) all together. The Harmony Search algorithm has the following merits:

HS does not require differential gradients, thus it can consider discontinuous functions as well as continuous functions.
HS can handle discrete variables as well as continuous variables.
HS does not require initial value setting for the variables.
HS is free from divergence.
HS may escape local optima.
HS may overcome the drawback of GA's building block theory which works well only if the relationship among variables in a chromosome is carefully considered. If neighbor variables in a chromosome have weaker relationship than remote variables, building block theory may not work well because of crossover operation. However, HS explicitly considers the relationship using ensemble operation.
HS has a novel stochastic derivative applied to discrete variables, which uses musician's experiences as a searching direction.
Certain HS variants do not require algorithm parameters such as HMCR and PAR, thus novice users can easily use the algorithm.

1 Basic Harmony Search Algorithm
2 Other Related Algorithms
3 References
4 Source Codes

Basic Harmony Search Algorithm

Harmony search tries to find a vector $\mathbf{x}$ which optimizes (minimizes or maximizes) a certain objective function.

The algorithm has the following steps:

Step 1: Generate random vectors ( $\mathbf{x}^1, \ldots, \mathbf{x}^{hms}$ ) as many as $hms$ (harmony memory size), then store them in harmony memory (HM).

$\mathbf{HM} = \begin{bmatrix} x^1_1 & \cdots & x^1_n & | & f(\mathbf{x}^1)\\ \vdots & \ddots & \vdots & | & \vdots\\ x^{hms}_1 & \cdots & x^{hms}_n & | & f(\mathbf{x}^{hms})\\ \end{bmatrix}.$

Step 2: Generate a new vector $\mathbf{x}'$ . For each component $x^'_i$ ,

with probability $hmcr$ (harmony memory considering rate; 0 ≤ $hmcr$ ≤ 1), pick the stored value from HM: $x^'_i \leftarrow x^{int(u(0, 1)*hms)%2B1}_i$
with probability $1-hmcr$ , pick a random value within the allowed range.

Step 3: Perform additional work if the value in Step 2 came from HM.

with probability $par$ (pitch adjusting rate; 0 ≤ $par$ ≤ 1), change $x^'_i$ by a small amount: $x^'_i \leftarrow x^'_i %2B \delta$ or $x^'_i \leftarrow x^'_i - \delta$ for discrete variable; or $x^'_i \leftarrow x^'_i %2B fw \cdot u(-1, 1)$ for continuous variable.
with probability $1-par$ , do nothing.

Step 4: If $\mathbf{x}^'$ is better than the worst vector $\mathbf{x}^{Worst}$ in HM, replace $\mathbf{x}^{Worst}$ with $\mathbf{x}'$ .

Step 5: Repeat from Step 2 to Step 4 until termination criterion (e.g. maximum iterations) is satisfied.

The parameters of the algorithm are

$hms$ = the size of the harmony memory. It generally varies from 1 to 100. (typical value = 30)
$hmcr$ = the rate of choosing a value from the harmony memory. It generally varies from 0.7 to 0.99. (typical value = 0.9)
$par$ = the rate of choosing a neighboring value. It generally varies from 0.1 to 0.5. (typical value = 0.3)
$\delta$ = the amount between two neighboring values in discrete candidate set.
$fw$ (fret width, formerly bandwidth) = the amount of maximum change in pitch adjustment. This can be (0.01 × allowed range) to (0.001 × allowed range).

It is possible to vary the parameter values as the search progresses, which gives an effect similar to simulated annealing.

Parameter-setting-free researches have been also performed. In the researches, algorithm users do not need tedious parameter setting process.

Other Related Algorithms

Harmony search lies in the fields of:

Evolutionary computing
- Metaheuristics
  - Stochastic optimization
    - Optimization

Other evolutionary computing methods include:

Evolutionary algorithms, including:
- Genetic algorithms
Swarm algorithms, including:

Other metaheuristic methods include:

Other stochastic methods include:

Cross-entropy method

References

General Information

Theory of Harmony Search

Original Harmony Search: Geem ZW, Kim JH, and Loganathan GV, A New Heuristic Optimization Algorithm: Harmony Search, Simulation, 2001.

Stochastic Partial Derivative: Geem ZW, Novel Derivative of Harmony Search Algorithm for Discrete Design Variables, Applied Mathematics and Computation, 2008.

Ensembled Harmony Search: Geem ZW, Improved Harmony Search from Ensemble of Music Players, Lecture Notes in Artificial Intelligence, 2006.

Continuous Harmony Search: Lee KS and Geem ZW, A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice, Computer Methods in Applied Mechanics and Engineering, 2005.

Exploratory Power of Harmony Search: Das S, Mukhopadhyay A, Roy A, Abraham A, Panigrahi BK, Exploratory Power of the Harmony Search Algorithm: Analysis and Improvements for Global Numerical Optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 41(1), 2011.

Improved Harmony Search: Mahdavi M, Fesanghary M, and Damangir E, An Improved Harmony Search Algorithm for Solving Optimization Problems, Applied Mathematics and Computation, 2007.

Particle-Swarm Harmony Search: Omran MGH and Mahdavi M, Global-Best Harmony Search, Applied Mathematics and Computation, 2008.

Hybrid Harmony Search: Fesanghary M, Mahdavi M, Minary-Jolandan M, and Alizadeh Y, Hybridizing Harmony Search Algorithm with Sequential Quadratic Programming for Engineering Optimization Problems, Computer Methods in Applied Mechanics and Engineering, 2008.

Parameter-Setting-Free Harmony Search: Geem ZW and Sim K-B, Parameter-Setting-Free Harmony Search Algorithm, Applied Mathematics and Computation, 2010.

Applications in Computer Science

Music Composition: Geem, Z. W. and Choi, J. Y. Music Composition Using Harmony Search Algorithm, Lecture Notes in Computer Science, 2007.

Sudoku Puzzle: Geem, Z. W. Harmony Search Algorithm for Solving Sudoku, Lecture Notes in Artificial Intelligence, 2007.

Tour Planning: Geem, Z. W., Tseng, C. -L., and Park, Y. Harmony Search for Generalized Orienteering Problem: Best Touring in China, Lecture Notes in Computer Science, 2005.

Visual Tracking: J. Fourie, S. Mills and R. Green Visual tracking using the harmony search algorithm, Image and Vision Computing New Zealand, 2008. 23rd International Conference

Visual Tracking: Jaco Fourie, Steven Mills, Richard Green, Harmony Filter: A Robust Visual Tracking System Using the Improved Harmony Search Algorithm, Image and Vision Computing (2010), doi:10.1016/j.imavis.2010.05.006

Visual Correspondence: J. Fourie, S. Mills and R. Green Directed correspondence search: Finding feature correspondences in images using the Harmony Search algorithm, Image and Vision Computing New Zealand, 23-25 Nov. 2009. 24rd International Conference

Image Deconvolution: J. Fourie, S. Mills and R. Green Counterpoint Harmony Search: An accurate algorithm for the blind deconvolution of binary images, Audio Language and Image Processing (ICALIP), 2010 International Conference on, Shanghai, China

Applications in Engineering

Fuzzy Data Clustering: Malaki, M.,Pourbaghery, JA, A Abolhassani, H. A combinatory approach to fuzzy clustering with harmony search and its applications to space shuttle data, Proceedings of the SCIS & ISIS,17–21,2008.

Structural Design: Lee, K. S. and Geem, Z. W. A New Structural Optimization Method Based on the Harmony Search Algorithm, Computers & Structures, 2004.

Structural Design: Saka, M. P. Optimum Geometry Design of Geodesic Domes Using Harmony Search Algorithm, Advances in Structural Engineering, 2007.

Water Network Design: Geem, Z. W. Optimal Cost Design of Water Distribution Networks using Harmony Search, Engineering Optimization, 2006.

Vehicle Routing: Geem, Z. W., Lee, K. S., and Park, Y. Application of Harmony Search to Vehicle Routing, American Journal of Applied Sciences, 2005.

Ground Water Modeling: Ayvaz, M. T. Simultaneous Determination of Aquifer Parameters and Zone Structures with Fuzzy C-Means Clustering and Meta-Heuristic Harmony Search Algorithm, Advances in Water Resources, 2007.

Soil Stability Analysis: Cheng, Y. M., Li, L., Lansivaara, T., Chi, S. C. and Sun, Y. J. An Improved Harmony Search Minimization Algorithm Using Different Slip Surface Generation Methods for Slope Stability Analysis, Engineering Optimization, 2008.

Energy System Dispatch: Vasebi, A., Fesanghary, M., and Bathaeea, S.M.T. Combined Heat and Power Economic Dispatch by Harmony Search Algorithm, International Journal of Electrical Power & Energy Systems, 2007.

Offshore Structure Mooring: Ryu, S., Duggal, A.S., Heyl, C. N., and Geem, Z. W. Mooring Cost Optimization via Harmony Search, Proceedings of the 26th International Conference on Offshore Mechanics and Arctic Engineering (OMAE 2007), ASME, San Diego, CA, USA, June 10-15 2007.

Hydrologic Parameter Calibration: Kim, J. H., Geem, Z. W., and Kim, E. S. Parameter Estimation of the Nonlinear Muskingum Model using Harmony Search, Journal of the American Water Resources Association, 2001.

Satellite Heat Pipe Design: Geem, Z. W. and Hwangbo, H. Application of Harmony Search to Multi-Objective Optimization for Satellite Heat Pipe Design, Proceedings of US-Korea Conference on Science, Technology, & Entrepreneurship (UKC 2006), CD-ROM, Teaneck, NJ, USA, Aug. 10-13 2006.

Dam Scheduling: Geem, Z. W. Optimal Scheduling of Multiple Dam System Using Harmony Search Algorithm, Lecture Notes in Computer Science, 2007.

Ecological Conservation: Geem, Z. W. and Williams, J. C. Ecological Optimization Using Harmony Search, Proceedings of American Conference on Applied Mathematics, Harvard University, Cambridge, MA, USA, March 24-26, 2008.

Heat exchanger design: Fesanghary, M., Damangir, E. and Soleimani, I. Design optimization of shell and tube heat exchangers using global sensitivity analysis and harmony search, Applied Thermal Engineering, In press.

Heat exchanger design: Doodman, A., Fesanghary, M. and Hosseini, R. A robust stochastic approach for design optimization of air cooled heat exchangers, Applied Energy, In press.

Heat exchanger network design: Khorasani, R.M., Fesanghary, M. A novel approach for synthesis of cost-optimal heat exchanger networks, Computers and Chemical Engineering, In press.

Face milling: Zarei, O., Fesanghary, M., Farshi, B., Jalili Saffar, R. and Razfar, M.R. Optimization of multi-pass face-milling via harmony search algorithm, Journal of Materials Processing Technology, In press.

Document Clustering: ,Mahdavi., M., Chehreghania, H., Abolhassania, H., Forsati, R. Novel meta-heuristic algorithms for document clustering, AMC Journal

Multicast Routing: Forsat, R., Haghighat, M., Mahdavi, M.,Harmony search based algorithms for bandwidth-delay-constrained least-cost multicast routing, Computer Communications, Elsevier

Source Codes

Improved Harmony Search (MATLAB) [1]
Hybrid HS-SQP (Visual C++) [2]
Multiobjective Harmony Search (C#) [3]
Other HS Variants [4]

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling ...

... functions

Golden section search · Interpolation methods · Line search · Successive parabolic interpolation

... and gradients

Convergence	Trust region · Wolfe conditions

Quasi–Newton	BFGS and L-BFGS · DFP · Symmetric rank-one (SR1)

Other methods	Gauss–Newton · Gradient · Levenberg–Marquardt · Conjugate gradient

... and Hessians

Newton's method

Constrained nonlinear

General	Barrier methods · Penalty methods

Differentiable	Augmented Lagrangian methods · Sequential quadratic programming · Successive linear programming

Convex minimization

General

Interior point method · Reduced gradient (Frank–Wolfe) · Subgradient method · Cutting-plane method

Linear and
quadratic

Interior point	Ellipsoid method of Khachiyan · Projective algorithm of Karmarkar · Semidefinite programming

Basis-exchange	Simplex algorithm of Dantzig · Criss-cross algorithm · Principal pivoting algorithm of Lemke